//O(logN)
func searchMatrix(matrix [][]int, target int) bool {
	m, n := len(matrix), len(matrix[0])
	if m == 1 && n == 1 {
		return matrix[0][0] == target
	}
	left, right := 0, m*n
	for left < right {
		mid := left + (right-left)/2
		if val := matrix[mid/n][mid%n]; val == target {
			return true
		} else if val < target {
			left++
		} else {
			right--
		}
	}
	return false
}
